package my.study.java.basic.algorithm.sorts;

import java.util.Random;

/**
 * 希尔排序通过比较一定间距的元素来工作，各趟比较所用的距离随着算法的进行而减少，
 * 直到只比较相邻元素的最后一趟排序为止
 * 利用了快速排序最优复杂度O(N)
 * 不同希尔增量最坏情况运行时间不同，最差为O(N^2)，采用Hibbard增量，最坏运行时间为O(N^3/2)
 * @author fanhongjie
 */
public class ShellSort {
	private static final int N = 20;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Element array[] = new Element[N];
		Random random = new Random();
		int ShellIncrement = 1;
		for (int i = 0; i < N; i++) {
			array[i] = new Element(random.nextInt(2 * N));
		}
		System.out.print("Init:\t");
		for (int i = 0; i < N; i++) {
			System.out.print(array[i].getValue() + "\t");
		}
		System.out.println();
		// Shell Sort()
		while (ShellIncrement * 9 < N) {
			ShellIncrement = ShellIncrement * 3 + 1;
		}
		for (; ShellIncrement >= 1; ShellIncrement /= 3) {
			for (int i = ShellIncrement; i < N ; i += ShellIncrement) {
				int j = i;
				Element temp = array[i];
				while (j >= ShellIncrement && temp.compareTo(array[j - ShellIncrement]) < 0) {
					array[j] = array[j - ShellIncrement];
					j -= ShellIncrement;
				}
				array[j] = temp;
			}
			System.out.print(ShellIncrement + ":\t");
			for (int k = 0; k < N; k++) {
				System.out.print(array[k].getValue() + "\t");
			}
			System.out.println();
		}
	}

}
